package com.gump.essay.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @auther zzc
 * @date 2021 03 27
 */
public class 二叉搜索树中第k小的元素 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    //利用深度优先遍历的的中序升序遍历  左中右节点   返回第k-1下标的元素   dfs
    public static void main(String[] args) {

        //存放遍历后升序树节点
        int k = 6;
        TreeNode treeNode = new TreeNode();
        List dfs = dfs(treeNode);
        System.out.println(dfs.get(k - 1));

    }

    private static List dfs(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) {
            return null;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
        return list;
    }
}
